// 文件名：map_range_trim.cpp
// 目的：维护一组不重叠的整数半开区间 [start, end)，支持区间插入（自动合并）与减法（切割）。
// 接口：
//   - insertRange(ranges, s, e)：插入区间 [s,e)，合并所有与其“相交或相邻”的区间；
//   - subtractRange(ranges, s, e)：从集合中减去 [s,e)，可能将区间切割为左右两段；
// 设计要点：
//   - map<int,int> 中 key 为 start，value 为 end，保持按 start 有序；
//   - 插入：从 lower_bound(s) 前一段开始，合并所有满足 first <= e 且 second >= s 的区间；
//   - 减法：遍历与 [s,e) 有交集的区间，按需裁剪与分裂；
//   - 复杂度：按命中区间数量近似 O(K log N)（插入/擦除为对数）。
// 注意：
//   - 区间为半开，端点相邻视为可合并（例如 [10,20) 与 [20,30) -> [10,30)）。

#include <iostream>
#include <map>

using RangeMap = std::map<int, int>; // key=start, value=end (半开区间)

void insertRange(RangeMap& ranges, int start, int end) {
    if (start >= end) return;
    auto it = ranges.lower_bound(start);
    if (it != ranges.begin()) --it;

    while (it != ranges.end() && it->second < start) ++it;

    int newStart = start;
    int newEnd = end;
    while (it != ranges.end() && it->first <= end) {
        newStart = std::min(newStart, it->first);
        newEnd = std::max(newEnd, it->second);
        it = ranges.erase(it);
    }
    ranges.emplace(newStart, newEnd);
}

void subtractRange(RangeMap& ranges, int start, int end) {
    if (start >= end) return;
    auto it = ranges.lower_bound(start);
    if (it != ranges.begin()) --it;

    while (it != ranges.end() && it->first < end) {
        if (it->second <= start) {
            ++it;
            continue;
        }
        int s = it->first;
        int e = it->second;
        it = ranges.erase(it);
        if (s < start) ranges.emplace(s, start);
        if (end < e) {
            ranges.emplace(end, e);
            break;
        }
    }
}

int main() {
    RangeMap ranges;
    insertRange(ranges, 10, 20);
    insertRange(ranges, 30, 40);
    insertRange(ranges, 18, 35);

    subtractRange(ranges, 12, 14);
    subtractRange(ranges, 32, 38);

    std::cout << "Ranges after operations:\n";
    for (const auto& [s, e] : ranges) {
        std::cout << "  [" << s << ", " << e << ")\n";
    }
    return 0;
}